package 力扣日常刷题.木23一月.第02天302;

/**
 * @author 帅小伙
 * @date 2022/3/2
 * @description
 */
public class Demo13归并排序 {


    public static void main(String[] args) {
        Demo13归并排序 test = new Demo13归并排序();
        int[] arr = test.sort(new int[]{1,4,3,2,6});
        for (int i : arr) {
            System.out.print(i+" ");
        }
    }

    int[] nums,tmp;
    public int[] sort(int nums[]){
        this.nums = nums;
        tmp = new int[nums.length];
        mergeSort(0,nums.length - 1);
        return nums;
    }

    public void mergeSort(int l,int r){
        if(l >= r) return;
        int m = (l+r) >> 1;
        mergeSort(l,m);
        mergeSort(m+1,r);
        int i = l,j = m + 1;
        for (int k = l; k <= r; k++) {
            tmp[k] = nums[k];
        }

        for (int k = l; k <= r; k++) {
            if(i == m+1){
                nums[k] = tmp[j++];
            }else if(j == r+1 || tmp[i] <= tmp[j]){
                nums[k] = tmp[i++];
            }else{
                nums[k] = tmp[j++];
            }
        }
    }
}
